home *** CD-ROM | disk | FTP | other *** search
/ Night Owl 6 / Night Owl's Shareware - PDSI-006 - Night Owl Corp (1990).iso / 039a / mawk.zip / ARRAY.C next >
C/C++ Source or Header  |  1991-04-07  |  6KB  |  236 lines
  1.  
  2. /********************************************
  3. array.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the Awk programming language as defined in
  8. Aho, Kernighan and Weinberger, The AWK Programming Language,
  9. Addison-Wesley, 1988.
  10.  
  11. See the accompaning file, LIMITATIONS, for restrictions
  12. regarding modification and redistribution of this
  13. program in source or binary form.
  14. ********************************************/
  15.  
  16. /* $Log:    array.c,v $
  17.  * Revision 2.1  91/04/08  08:22:15  brennan
  18.  * VERSION 0.97
  19.  * 
  20. */
  21.  
  22. #include "mawk.h"
  23. #include "symtype.h"
  24. #include "memory.h"
  25. #include "bi_vars.h"
  26.  
  27. extern int returning ; 
  28.    /* flag -- on if returning from function call */
  29.  
  30. extern unsigned hash() ;
  31.  
  32. /* An array A is a pointer to a hash table of size
  33.    A_HASH_PRIME holding linked lists of ANODEs.
  34.  
  35.    When an index is deleted via  delete A[i], the
  36.    ANODE is not removed from the hash chain.  A[i].cp
  37.    and A[i].sval are both freed and sval is set NULL.
  38.    This method of deletion simplifies for( i in A ) loops.
  39. */
  40.  
  41. /* is sval in A ? */
  42. int array_test( A, sval)
  43.   ARRAY A ; 
  44.   STRING *sval ;
  45. { char *s = sval->str ;
  46.   register ANODE *p = A[ hash(s) % A_HASH_PRIME ] ;
  47.   
  48.   while ( p )
  49.   { if ( p->sval && strcmp(s, p->sval->str) == 0 )  return 1 ;
  50.     p = p->link ; }
  51.   /* not there */
  52.   return 0 ;
  53. }
  54.   
  55. /* find x in array a
  56.    if flag is ON x is a char* else a STRING*,
  57.    computes a[x] as a CELL*
  58. */
  59.  
  60. CELL *array_find( a, x, flag)
  61.   ARRAY a ; PTR  x ; int flag ;
  62. { register ANODE *p ;  /* search with p */
  63.   ANODE *q ;  /* pts at a deleted node */
  64.   unsigned h ;
  65.   char *s ;
  66.  
  67.   s = flag ? (char *) x : ( (STRING *) x) -> str ;
  68.   p = a[ h = hash(s) % A_HASH_PRIME ] ;
  69.   q = (ANODE *) 0 ; 
  70.  
  71.   while ( p )
  72.   { 
  73.     if ( p->sval )
  74.     {
  75.       if ( strcmp(s,p->sval->str) == 0 )  /* found */
  76.         return  p->cp ;
  77.     }
  78.     else /* a deleted node */
  79.     if ( !q )  q = p ;
  80.  
  81.     p = p->link ;
  82.   }
  83.   
  84.   /* not there make one  */
  85.   if ( q )  p = q ; /* reuse the node */
  86.   else
  87.   { p = (ANODE *) zmalloc( sizeof(ANODE) ) ;
  88.     p->link = a[h] ; a[h] = p ; }
  89.  
  90.   if ( flag )  p->sval = new_STRING(s) ;
  91.   else
  92.   { p->sval = (STRING *) x ; p->sval->ref_cnt++ ; }
  93.   p->cp = new_CELL() ; p->cp->type = C_NOINIT ;
  94.   return p->cp ;
  95. }
  96.  
  97. void  array_delete( a, sval)
  98.   ARRAY a ; STRING *sval ;
  99. { char *s = sval->str ;
  100.   register ANODE *p = a[ hash(s) % A_HASH_PRIME ] ;
  101.  
  102.   while ( p )
  103.   { if ( p->sval && strcmp(s, p->sval->str)== 0 ) /* found */
  104.     { 
  105.       cell_destroy(p->cp) ;  free_CELL(p->cp) ;
  106.       free_STRING(p->sval) ; p->sval = (STRING *) 0 ;
  107.  
  108.       break ;
  109.     }
  110.  
  111.     p = p->link ;
  112.   }
  113. }
  114.       
  115.  
  116. /* for ( i in A ) ,
  117.    loop over elements of an array 
  118.  
  119. sp[0].ptr :  a pointer to A ( the hash table of A)
  120. sp[-1] :  a pointer to i ( a cell ptr)
  121.  
  122. cdp[0] :  a stop op to catch breaks
  123. cdp[1] :  offset from cdp of the code after the loop (n+2)
  124. cdp[2] :  start of body of the loop
  125. cdp[3..n] : the rest of the body
  126. cdp[n+1]  : a stop op to delimit the body and catch continues
  127. */
  128.  
  129. INST  *array_loop( cdp, sp, fp) /* passed code, stack and frame ptrs */
  130.   INST *cdp ; 
  131.   CELL *sp, *fp ;
  132. { int i ;
  133.   register ANODE *p ;
  134.   ARRAY   A = (ARRAY) sp-- -> ptr ;
  135.   register CELL *cp = (CELL *) sp-- -> ptr ;
  136.  
  137.   for ( i = 0 ; i < A_HASH_PRIME ; i++ )
  138.   for ( p = A[i] ; p ; p = p->link )
  139.   { if ( ! p->sval /* its deleted */ )  continue ;
  140.   
  141.     cell_destroy(cp) ;
  142.     cp->type = C_STRING ;
  143.     cp->ptr = (PTR) p->sval ;
  144.     p->sval->ref_cnt++ ;
  145.  
  146.     /* execute the body of the loop */
  147.     if ( execute(cdp+2, sp, fp) == cdp /* exec'ed a break statement */
  148.          || returning  /* function return in body of loop */
  149.        )  
  150.            goto break2 /* break both for loops */ ; 
  151.   }
  152.  
  153. break2 :
  154.   return   cdp + cdp[1].op ;
  155. }
  156.  
  157.  
  158. /* cat together cnt elements on the eval stack to form
  159.    an array index using SUBSEP */
  160.  
  161. CELL *array_cat( sp, cnt)
  162.   register CELL *sp ;
  163.   int cnt ;
  164. { register CELL *p ;  /* walks the stack */
  165.   CELL subsep ;  /* a copy of bi_vars[SUBSEP] */
  166.   unsigned subsep_len ;
  167.   char *subsep_str ;
  168.   unsigned total_len ; /* length of cat'ed expression */
  169.   CELL *top ;  /* sp at entry */
  170.   char *t ; /* target ptr when catting */
  171.   STRING *sval ;  /* build new STRING here */
  172.  
  173.   /* get a copy of subsep, we may need to cast */
  174.   (void) cellcpy(&subsep, bi_vars + SUBSEP) ;
  175.   if ( subsep.type < C_STRING ) cast1_to_s(&subsep) ;
  176.   subsep_len = string(&subsep)->len ;
  177.   subsep_str = string(&subsep)->str ;
  178.   total_len = --cnt * subsep_len ;
  179.  
  180.   top = sp ;
  181.   sp -= cnt ;
  182.   for( p = sp ; p <= top ; p++ )
  183.   {
  184.     if ( p->type < C_STRING ) cast1_to_s(p) ;
  185.     total_len += string(p)->len ;
  186.   }
  187.  
  188.   sval = new_STRING((char *)0, total_len) ;
  189.   t = sval->str ;
  190.  
  191.   /* put the pieces together */
  192.   for( p = sp ; p < top ; p++ )
  193.   { (void) memcpy(t, string(p)->str, string(p)->len) ;
  194.     (void) memcpy( t += string(p)->len, subsep_str, subsep_len) ;
  195.     t += subsep_len ;
  196.   }
  197.   /* p == top */
  198.   (void) memcpy(t, string(p)->str, string(p)->len) ;
  199.  
  200.   /* done, now cleanup */
  201.   free_STRING(string(&subsep)) ;
  202.   while ( p >= sp )  { free_STRING(string(p)) ; p-- ; }
  203.   sp->type = C_STRING ;
  204.   sp->ptr = (PTR) sval ;
  205.   return sp ;
  206. }
  207.  
  208.  
  209. /* free all memory used by an array,
  210.    only used for arrays local to a function call
  211. */
  212.  
  213. void  array_free(A)
  214.   ARRAY  A ;
  215. { register ANODE *p ;
  216.   register int i ;
  217.   ANODE *q ;
  218.  
  219.   for( i = 0 ; i < A_HASH_PRIME ; i++ )
  220.   { p = A[i] ;
  221.     while ( p )
  222.     { /* check its not a deleted node */
  223.       if ( p->sval )
  224.       { free_STRING(p->sval) ;
  225.         cell_destroy(p->cp) ;
  226.         free_CELL(p->cp) ;
  227.       }
  228.  
  229.       q = p ; p = p->link ;
  230.       zfree( q, sizeof(ANODE)) ;
  231.     }
  232.   }
  233.  
  234.   zfree(A, sizeof(ANODE *) * A_HASH_PRIME ) ;
  235. }
  236.